Reconstruct Itinerary

Description#

Assume we have an array of airline tickets represented as pairs of departure and arrival airports like [from, to]. We have to reconstruct the itinerary in order. All tickets belong to a man who departs from a specified location, e.g., JFK. Therefore, the itinerary must begin with JFK. There might be multiple valid itineraries; you must return the itinerary with the smallest lexical order.

Constraints#

Consider the following constraints:

• 1 <= tickets.length <= 300
• tickets[i].length must be 2.
• $from_i.length$, $to_i.length$ == 3
• $from_i$ and $to_i$ consist of uppercase English letters.
• Specified departure must be the start point of itinerary.
• $from_i$ and $to_i$ would not be equal.
• Must use all the tickets but only once.

Let’s try to understand the problem with the help of an example:

Coding exercise#

Solution#

We have an array containing departure and arrival pairs. We assume this problem as a graph, where the vertices of the graph represent airports and edges represent a flight between the airports.

Let’s see an algorithm for the described problem below:

1. First, we create a hash map with keys for each departure point. The value for a given key is an alphabetically sorted list of all airports to which the passenger flew from the airport represented by the given key.

2. Next, we will append the start vertex to a string.

3. Then, we will perform a post-order depth-first search (DFS) from the start vertex where the visit operation comprises appending a visited vertex to a list of strings.

4. Once all vertices have been visited, reverse the list to get the result.

This way, we will get a valid itinerary that visits all the airports. We could assume the algorithm as the postorder depth-first search in a graph, with a fixed start vertex.

Let’s see the following illustration to understand this algorithm.

Removing an element from the beginning of the array takes $O(n)$ time which increases the overall program’s time complexity. Therefore, we will use the pop() method, which takes $O(1)$ time to remove an element from the end of the array. For this, we have to store the array in descending order.

Let’s see the following illustration after applying the described changes.

Let’s have a look at the solution code below:

Complexity measures#

Time complexity#

• First, we add tickets into the map object. The time complexity of this operation is $O(e)$, where e is the number of flights.

• The DFS() method performs the pop() method in $O(1)$ time, so, the total time complexity of the DFS() method will be $O(v+e)$, where v represents the number of airports and e represents the number of flights.

• The sort() method takes $O(e$ $log$ $e)$ time.

The worst-case time complexity of the sort() method is dominant. Therefore, the time complexity of the detect_itinerary() method would be $O(e$ $log$ $e)$ in the worst case.

Space complexity#

The worst-case space complexity of this problem is $O(v+e)$ where v is the number of airports and e is the number of flights. The maximum function call stack depth for the DFS() function is $O(e)$. As a result, the total space complexity of the detect_itinerary() method will be $O(v+2e)$ = $O(v+e)$.